The present invention relates generally to an improved data processing system and in particular to a method and apparatus for probing a hash table in a memory device.
Emerging processors provide growing computation power by increasing the number of processing cores, by increasing the degree of hyper-threading, and/or by vector processing. However, the amount of available cache or memory for such processors remains limited. As a result, the amount of available cache per processing core is reduced. There are more cores (and hence more threads) issuing more memory I/O requests, which causes an executing program to encounter a memory bandwidth limit (also know as a memory wall). The memory bandwidth problem results in a performance bottleneck which prevents linear performance scaling with increasing number of processing cores (and threads).
Hashing is a commonly used technique for providing access to data based on a key in constant expected time. Hashing is used in database systems for joins, aggregation, duplicate-elimination, and indexing. In a database context, hash keys are typically single column values or a tuple of values for a small number of columns. Payloads in a hash table may be full records, pointers, or record identifiers, to records, or they may represent values of an aggregate computed using hash aggregation.
Conventional hash tables perform poorly, in terms of time required for hashing, on processors due to branch mispredictions, cache misses, and poor instruction-level parallelism. Conventional hash tables also have space overheads. Further, conventional approaches do not address the decreasing per-core-cache-size and resulting performance limitations.